using System;
using System.Collections.Generic;
using System.Text;

namespace Mono.Boost.Graph
{//todo test it out !!!
    public class Match
    {
        /// <summary>
        /// O( |V|^(1/2) * |E| )
        /// </summary>
        /// <param name="g">g must be biparate by Pivot</param>
        /// <param name="Pivot"></param>
        /// <param name="Match"></param>
        public void HopcroftKarp(IGraph g, uint Pivot, out IDictionary<uint, uint> Match)
        {
            Match = g.createVertexPropertyMap<uint>();

            uint time = 0;
            Queue<uint> q = new Queue<uint>();
            Stack<IEnumerator<EdgeInfo>> se = new Stack<IEnumerator<EdgeInfo>>();
            Stack<uint> sid = new Stack<uint>();
            Stack<uint> sd = new Stack<uint>();
            IDictionary<uint, uint> d = g.createVertexPropertyMap<uint>();
            bool cont;
            do
            {
                cont = false;
                q.Clear();
                d.Clear();
                se.Clear();
                sid.Clear();
                time++;
                for (uint i = 0; i < Pivot; i++)
                {
                    if (!Match.ContainsKey(i))
                    {
                        q.Enqueue(i);
                        d[i] = 0;
                        sid.Push(i);
                        se.Push(g.outgoing(i).GetEnumerator());
                        //                        sd.Push(0);
                    }
                }
                //BFS
                while (q.Count != 0)
                {
                    uint cur = q.Dequeue();
                    foreach (EdgeInfo v in g.outgoing(cur))
                    {
                        if (!d.ContainsKey(v.v))
                        {
                            d[v.v] = d[cur] + 1;
                            q.Enqueue(v.v);
                        }
                    }
                }

                for (uint i = 0; i < Pivot; i++)
                    if (d.ContainsKey(i) && d[i] == 0)
                    {
                        sid.Push(i);
                        se.Push(g.outgoing(i).GetEnumerator());
                
                        //part-DFS
                        int level = 0;
                        while (sid.Count != 0)
                        {
                            uint tmp;

                            while (true)
                            {

                                if (sid.Count % 2 == 0)
                                {
                                    tmp = sid.Peek();
#if Debug
                                    //if (tmp = null) throw exception("HK Math bad implementation (uint tmp)"); 
#endif
                                    if (!Match.ContainsKey(tmp))//succes
                                    {
                                        cont = true;
                                        uint cur;
                                        uint prev = sid.Pop();
                                        while (sid.Count != 0)
                                        {
                                            cur = prev;
                                            prev = sid.Pop();
                                            if (sid.Count % 2 == 0)
                                            {
                                                Match.Remove(cur);
                                                Match.Remove(prev);
                                            }
                                            else
                                            {
                                                Match.Add(cur, prev);
                                                Match.Add(prev, cur);
                                            }
                                        }
                                        break;
                                    }
                                    tmp = Match[tmp];
                                    if (d.ContainsKey(tmp))
                                        if (d[tmp] == level + 1)
                                        {
                                            sid.Push(tmp); d.Remove(tmp);
                                            se.Push(g.outgoing(tmp).GetEnumerator());
                                            level++;
                                        }
                                        else
                                        {
                                            se.Pop();
                                            sid.Pop();
                                            level--;
                                        }
                                }
                                else //first 
                                {
                                    IEnumerator<EdgeInfo> e = se.Peek();
                                    if (!e.MoveNext())
                                    {
                                        if (level != 0)
                                        {
                                            se.Pop();
                                            level -= 2;
                                            sid.Pop(); sid.Pop();
                                        } break;
                                    }
                                    if (d.ContainsKey(tmp = e.Current.v))
                                        if (d[tmp] == level + 1)
                                        {
                                            level++;
                                            sid.Push(tmp); d.Remove(tmp);
#if Debug
                            if (sid.Count != 2 * se.Count) throw exception("HK Math bad implementation"); 
                            if (level!= sid.Count-1) throw exception("HK Math bad implementation (uint level)"); 
#endif
                                            break;
                                        }
                                }
                            }
                        }
                    }

            }
            while (cont);
        }
    }
}
